class Solution:
    """
    91. 解码方法
    https://leetcode-cn.com/problems/decode-ways/submissions/
    @date: 2020年12月31日16:58:09
    @author: mizzle rain
    """
    def numDecodings(self, s: str) -> int:
        s = ' ' + s
        n = len(s)
        # dp[i] 表示s[0 .. i]一共有几种解码方法
        dp = [0 for _ in range(n)]
        for i in range(n):
            if i == 0:
                dp[0] = 1
                continue
            if s[i] != '0':
                dp[i] = dp[i-1]
            pre = int(s[i-1:i+1])
            if pre >= 10 and pre <= 26:
                dp[i] += dp[i-2]
        return dp[n-1]


if __name__ == '__main__':
    s = Solution()
    ans = s.numDecodings('10')
    print(ans)
